A communication system of this type has generally to provide communication between a substantial number of units which we will term end units, each of which may be assumed to have a globally unique address. In general, any end unit may want to send a message to any other end unit. Two general types or levels of communication system have become established for this purpose: switching networks and area networks.
In a switching network, there is a plurality of switching devices termed routers with various paths connecting the routers to the end units and to each other. The routers collectively have the responsibility for finding a path through the network between any two end units (source and destination). The routers therefore maintain various tables by means of which they can determine the required route for the message.
In a simple area network, there is a single communication channel to which all the end units are connected. Every end unit which wants to send a message puts the message on the communication channel, and each unit monitors the communication channel continuously for messages with its own address as destination. (A complication is that there is a need for some form of collision detection. A unit will not try to transmit a message if some other unit is already transmitting, but it is possible that two units might try to transmit messages simultaneously, in which case both transmissions must be aborted).
Each device attached to the network has an address which is unique (most device manufacturers and network managers conform to conventions which ensure this). A message directed to that device has that address included as a destination address field in the header of the message, and the device includes hardware which monitors all messages in the network for its own address.
The first major form of area network to be introduced on a large scale was termed a local area network (LAN), which was restricted to a physically small area (of dimensions of the order of 100 m).
Techniques for connecting LANs to switching networks were soon developed, wherein routers are coupled to LANs. As far as the switching network is concerned, each LAN is treated as a complex (multi-address) end unit. (A complication is that a LAN may often be coupled to more than one router; this requires the switching network to be able to cope with multiple possible paths).
The use of area networks has however expanded beyond the limitations of the original LAN systems.
One development is concerned with areas which are physically much larger. For this, various characteristics of the original LAN systems have been modified, to produce what are termed wide area networks (WANs). For present purposes, there is no fundamental distinction between LANs and WANs.
A more important development has been the linking of separate LANs by means of bridges; we shall call such a network an extended network and the individual LANs of the extended network its component networks. One reason for the development of this technique is to allow originally independent LANs to be connected together. The basic function of a bridge is to act as a store and forward device, passing messages from each of the LANs to which it is connected to the other LAN.
One problem which arises with such extended networks is that of network loading. With a network as described so far, all units use a common communication channel, which has a limited message carrying capacity. This therefore limits the size of an area network (ie the number of end units which it has). If an area network is an extended network consisting of a number of component networks coupled together by simple bridges, then all messages are propagated throughout the extended network, so the size of network which can be formed in this way is limited.
In the simplest form of system, each device has a single unique address. However, there are two possible modifications of this. It may be desirable to assign two or more addresses to a single device. But more importantly, it is sometimes desirable to send messages not to a single device but to all devices (termed broadcasting). For this, each device needs to be given not only its own unique address(es) but also a broadcast address shared with all other devices. It is also sometimes desirable to send messages to a particular group of devices (termed multicasting). For this, all devices of the group need to share a common multicast address. Further, it may be desirable to have a number of different multicast groups, with some devices belonging to several multicast groups.
The hardware address recognition circuitry of a device can obviously be expanded to recognize a number of different addresses, which may be of different types (unique and multicast--broadcast messages do not require address recognition). However, this increases the complexity of the devices. It is therefore common for certain relatively simple types of end unit to rely on software rather than hardware to determine whether messages are directed to the unit. A high message density can thus impose substantial processing loads on such end units.
It has been recognized that much of the message traffic on an extended network is between end units coupled to the same LAN of the network. It has therefore become known to provide the bridges between the different LANs of such a network with some form of filtering, which is intended to discriminate between messages which do and do not need to be passed through the bridge and to pass only the former.
To achieve this, the bridge must do more than act purely as a message transmission device which is effectively transparent. It must incorporate some means for examining the messages reaching it to determine whether or not to pass them on.
To understand the manner in which such filtering is achieved, the structure of messages in area networks must be considered in more detail. There is a number of different message formats, developed by different organizations. However, the general structures of these formats are sufficiently similar to allow them all to be used on the same network (in particular, they have a common header structure as far as the source and destination addresses are concerned). The different formats contain keys which allow them to be distinguished. In addition to this, there are various message types or classes, such as date messages and various kinds of control messages, or individual, multicast, and broadcast, again distinguished by suitable keys. These latter keys may be regarded either as bits forming part of the addresses or as components of the message type or class. We shall use the term protocol identifier for the combination of all these components.
The main known bridge filtering technique is termed blackball filtering. In this, a number of specific values or characteristics for different component (source address, destination address, and protocol identifier) of the messages are specified. (This technique includes the more specific techniques of protocol, type filtering, destination filtering, and source filtering.)
In practice, the address structure of a network is normally largely hierarchical, so that the address of a particular end unit may for example be a sequence of elements consisting of a region identifier in the area network, a LAN identifier, a unit type identifier (eg PC, workstation, loadserver, communications server, etc) and a unit identifier. The filter value for an address may be any selected combination of source and/or destination address elements. Similarly, protocol and/or message types can consist of separate elements, and the filter value for these may consist of any selected combination of elements.
The filter mechanism stores these filter values and matches them against each message received by the bridge. If all the elements match, the message is filtered out, ie not transmitted by the bridge.
The filter mechanism can store a plurality of sets of values, matching each set against each incoming message. The message ie filtered out if it matches any of the stored sets of values. In other words, each set of values votes on the message, with a match producing a No vote; a single No vote "blackballs" (vetoes) the message, preventing it from being transmitted.
This filtering technique has some significant disadvantages, and the general object of the present invention is to provide an improved filtering technique which alleviates or overcomes these disadvantages.
A further problem arises with multiport bridges that is, with bridges which have more than 2 ports. There are broadly three possible modes of implementing filtering with such a bridge: bridge-based, port-based, or port-to-port. For bridge-based filtering, a single filter test is applied to all incoming messages regardless of which port they are received on, and each message is either transmitted to all ports or not transmitted at all. For port-based filtering, a separate filter test is applied to each port, and a message is transmitted or not depending on whether or not the test produces a match. This port-based filtering has three variants, depending on whether the filtering is applied to incoming messages, outgoing messages, or both. For port-to-port filtering, the bridge is treated as a group of 2-port bridges, each of which is filtered separately.
These three multiport techniques all have drawbacks. Bridge-based filtering is obviously extremely crude, and setting up the bridge so that it does not block the passage of any messages which must be allowed to pass through it results in a very low efficiency, ie only a small proportion of messages are blocked. Port-based filtering improves on this, but its efficiency is still limited since for each port, the filter must be coarse enough to allow through all messages which are to be sent to any other port (or all messages which may be received from any other port). Port-to-port filtering achieves the same efficiency as filtering for a 2-port bridge, but can easily be expensive or impossible to implement for bridges with a large number of ports, as a number of port-to-port pairs is proportional to the square of the number of ports.
The object of the present invention is to provide an improved bridge filtering technique, particularly though not exclusively applicable to multiport bridges with a large number of ports (eg 256 ports).
Underlying the present invention, there is a novel principle or concept, of domains and domain classes.
For a given message, a reachability domain (or simply domain) is the region of a network which that message needs to reach. The region consists of those component networks of the total (extended) network having potentially connected to the end units which need to receive that message (plus any more component networks required to make the domain connected, so that it does not consist of two or more parts not connected to each other). This domain is obviously the domain for all messages with identical characteristics (source address, destination address, and protocol identifier). Also, it may happen that there is a single domain common to messages with characteristics which are different. (In practice, the characteristics of the messages will probably vary only in certain respects.)
Since the message characteristics include the protocol identifier, different messages sent from a given unit may have different domains.
It is often useful to broaden the concept of a domain to describe the reachability component networks not just of messages with identical characteristics but of messages with similar characteristics, ie for which only some of the characteristics are identical. Thus the domains for two similar end units on the same component network will normally be the same.
One can also consider the domains for messages having the same protocol identifier. This is a further broadening of the concept of domains, since different messages having the same protocol identifier may not necessarily have the same domain. In particular, it may be desirable for a bridge to be asymmetric for some protocol identifiers. The domain for messages having the same protocol identifier can then be divided or factored into more limited domains for these different messages. These more limited domains can be distinguished by including the source address (which can in turn indicate the type of unit) as an essential part of the message characteristics.
It is convenient to group the domains into domain classes, though in a simple system, domains and domain classes can be the same. The domain classes are chosen so that all messages in the same domain class can be treated in the same way. The domains in a domain class are normally disjoint. For effective operation, it is important that each domain class should contain only one address/protocol type.
In the present system, a bridge contains domain assignment means for determining, from the characteristic of a message, a domain class; means for storing, for each output port, a set of domain classes; and means for transmitting the message on each output port for which the domain class of the message matches a stored domain class for that port. The means for determining domain classes preferably utilizes look-up tables, and the matching for the output ports preferably permits partial matching (ie allows "don't care" elements).
It will be realized that this technique is more abstract than the standard filtering techniques such as the blackball technique. When applied to a simple 2-port bridge, it involves a 2-stage process of first classifying the incoming message to generate a domain class and then matching the domain class. The second step of matching can be regarded as broadly analogous to the filtering of the blackball technique. The first step of classifying allows considerable generalization which is not feasible with simple blackball matching.
When applied to a multiport bridge, the present system is broadly similar to part filtering systems. The second step of the present system is broadly similar to output port filtering. The first step of the present system has some similarity with input port filtering to the extent that it is applied at input ports, but the present process of classification into domain classes has in itself little similarity with standard filtering.
Accordingly the present invention provides, in or for a bridge in an area network, message filtering means comprising means for generating respective class specifiers from the message source, message destination, and type of message; means for generating a class specification from the class specifiers; means for generating a domain class from the class specification; means for generating a domain list from the domain class; and means for generating a list of ports from the domain list.
Preferably, the generating means is provided by respective look-up means.
This means for generating, from the class specifiers, a class specification and the look-up means for generating, from the class specification, a domain class may comprise a single look-up table. The means for generating, from the class specifiers, a class specification may comprise concatenating means, or may alternatively comprise algorithmic logical combination means.
The message filtering means may also include dynamic filtering means the output of which is combined with the list of ports.
The invention also provides a bridge comprising a plurality of line cards, each including a respective processor and having at least one communications interface having a plurality of ports, coupled together by means of a bus and a common memory controlled by a central bridge processor, including the above message filtering means. At least some of the bridge ports may be logical ports. The look-up means may be contained in the common memory and the central bridge processor, or be distributed between the line cards, or be duplicated between the line cards. The look-up means on each line card may comprise a single look-up table encoding three transformations, so that its input is a class specification and its output is a reachability domain.
The present invention further provides, in or for a bridge in an area network, a method of filtering messages comprising generating respective class specifiers from the message source, message destination, and type of message; generating a class specification from the class specifiers; generating a domain class from the class specification; generating a domain list from the domain class; and generating a list of ports from the domain list.